package com.arron.algorithm.leetcodetop100.bfs;

import com.arron.algorithm.leetcodetop100.二叉树.BuildTree;
import com.arron.algorithm.tree.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class 二叉树最小深度 {

    int depth;
    int minDepth = Integer.MAX_VALUE;

    public int minDepth(TreeNode root) {
        if (root == null){
            return 0;
        }

       return  bfs(root);
    }



    public int bfs(TreeNode root){

        Queue<TreeNode> queue = new LinkedList<>();


        queue.offer(root);

        int depth = 1;
        while (!queue.isEmpty()){

            int size = queue.size();

            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();

                if (poll.left == null && poll.right == null){
                    return depth;
                }

                if (poll.left != null){
                    queue.offer(poll.left);
                }
                if (poll.right != null){
                    queue.offer(poll.right);
                }
            }

            depth++;

        }

        return depth;
    }



    // dfs 递归搜，搜索所有节点 0(N)
    public void dfs(TreeNode root){
        if (root == null){
            return;
        }
        depth++;

        if (root.left == null && root.right == null){
            minDepth = Math.min(minDepth,depth);
        }
        minDepth(root.left);
        minDepth(root.right);

        depth--;
    }

    public static void main(String[] args) {
        BuildTree buildTree = new BuildTree();
        TreeNode treeNode = buildTree.buildTree();
        二叉树最小深度 minDepth = new 二叉树最小深度();
        System.out.println(minDepth.minDepth(treeNode));
    }
}
